import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM58 字符串的排列
 * <a href="https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=295&tqId=23291&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2023-03-01
 * Time: 23:22
 */

public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<>();
        //判空处理
        if (str.length() == 0) {
            return res;
        }
        char[] charArray = str.toCharArray();
        //将charArray排为升序，方便应对重复的元素
        Arrays.sort(charArray);
        //创建标记数组，对应相同下标的字符是否已经被选过
        boolean[] flag = new boolean[charArray.length];
        //临时存放字符
        StringBuffer buffer = new StringBuffer();
        recursion(res,buffer,charArray,flag,0);
        return res;
    }

    /**
     * @param res       记录排列结果的链表
     * @param buffer    临时存放字符
     * @param charArray 存放字符的数组
     * @param flag      标记对应下标的字符是否已被选中
     * @param num       已选中的字符个数
     * @return
     */
    private void recursion(ArrayList<String> res, StringBuffer buffer, char[] charArray, boolean[] flag, int num) {
        if (num == charArray.length) {
            res.add(buffer.toString());
        } else {
            for (int i = 0; i < charArray.length; i++) {
                if (flag[i]) { //该字符已经被选过了
                    continue;
                }
                //应对重复字符
                if (i > 0 && charArray[i-1] == charArray[i] && flag[i-1]) {
                    //这里return和continue均可以实现，因为这本质就是划定了相连元素的使用顺序，即从
                    //后向前使用相同的元素，这里使用continue的话，就是加入aa相连，第一个a被选中了之
                    //后，其后面的所有递归路径均会被这里的continue破坏，而return可以直接结束这个子
                    //问题的递归，因此这里使用return会更好。（递归更少）
                    return;
                    //continue;
                }
                buffer.append(charArray[i]);
                flag[i] = true;
                recursion(res,buffer,charArray,flag,num+1);
                buffer.deleteCharAt(num);
                flag[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String str = "ab";
        ArrayList<String> res = solution.Permutation(str);
        System.out.println(res);
    }
}